package leetcode_1001_1100;

public class LeeCode_1043 {
    public static void main(String[] args) {
        System.out.println(maxSumAfterPartitioning(new int[]{1, 15, 7, 9, 2, 5, 10}, 3));
        System.out.println(maxSumAfterPartitioning(new int[]{1,4,1,5,7,3,6,1,9,9,3}, 4));
    }
    private static int maxSumAfterPartitioning(int[] arr, int k) {
        int n = arr.length;
        int[] dp = new int[n];
        int[] maxes = new int[n];
        int max = 0;
        for (int i = 0; i < n; i++) {
            if (arr[i] > max){
                max = arr[i];
            }
            maxes[i] = max;
        }
        for (int i = 0; i < n; i++) {
            if (i < k){
                dp[i] = maxes[i] * (i + 1);
            }
        }
        for (int i = k; i < n; i++) {
            max = 0;
            for (int j = 1; j <= k; j++) {
                int may = dp[i - j] + getMax(arr, i - j + 1, i) * j;
                if (may > max){
                    max = may;
                }
            }
            dp[i] = max;
        }
        return dp[n - 1];
    }
    private static int getMax(int[] arr, int s, int e){
        int max = 0;
        for (int i = s; i <= e; i++) {
            if (arr[i] > max){
                max = arr[i];
            }
        }
        return max;
    }
}
